#define _CRT_SECURE_NO_WARNINGS 1

#include <iostream>
#include <vector>
#include <iomanip>
#include <queue>
#include <algorithm>

struct Process {
    std::string name;
    int arrivalTime;
    int serviceTime;
    int remainingTime;
    int startTime;
    int endTime;
    float turnaroundTime;
    float weightedTurnaroundTime;
};

bool compareArrivalTimes(const Process& a, const Process& b) {
    return a.arrivalTime < b.arrivalTime;
}

void calculateTimes(std::vector<Process>& processes) {
    std::sort(processes.begin(), processes.end(), compareArrivalTimes);

    std::priority_queue<std::pair<int, int>, std::vector<std::pair<int, int>>, std::greater<std::pair<int, int>>> pq;
    int currentTime = 0;
    int index = 0;
    int n = processes.size();
    std::vector<bool> completed(n, false);
    std::vector<int> lastExecutionTime(n, -1);
    std::vector<int> startTimes(n, -1);
    std::vector<int> endTimes(n, -1);
    std::vector<std::string> executionOrder;

    while (index < n || !pq.empty()) {
        if (pq.empty() && currentTime < processes[index].arrivalTime) {
            currentTime = processes[index].arrivalTime;
        }

        while (index < n && currentTime >= processes[index].arrivalTime) {
            pq.push({ processes[index].remainingTime, index });
            index++;
        }

        if (!pq.empty()) {
            auto currentProcess = pq.top();
            pq.pop();
            int processIndex = currentProcess.second;

            if (startTimes[processIndex] == -1) {
                startTimes[processIndex] = currentTime;
            }

            processes[processIndex].remainingTime--;
            currentTime++;

            if (lastExecutionTime[processIndex] != currentTime - 1) {
                lastExecutionTime[processIndex] = currentTime - 1;
                executionOrder.push_back(processes[processIndex].name);
            }

            if (processes[processIndex].remainingTime == 0) {
                endTimes[processIndex] = currentTime;
                completed[processIndex] = true;
            }
            else {
                pq.push({ processes[processIndex].remainingTime, processIndex });
            }
        }
    }

    for (int i = 0; i < n; ++i) {
        processes[i].startTime = startTimes[i];
        processes[i].endTime = endTimes[i];
        processes[i].turnaroundTime = processes[i].endTime - processes[i].arrivalTime;
        processes[i].weightedTurnaroundTime = processes[i].turnaroundTime / processes[i].serviceTime;
    }

    // Remove duplicate consecutive entries in the execution order
    std::vector<std::string> uniqueExecutionOrder;
    if (!executionOrder.empty()) {
        uniqueExecutionOrder.push_back(executionOrder[0]);
        for (size_t i = 1; i < executionOrder.size(); ++i) {
            if (executionOrder[i] != executionOrder[i - 1]) {
                uniqueExecutionOrder.push_back(executionOrder[i]);
            }
        }
    }

    // Output the execution order
    std::cout << "\n调用抢占式短进程优先算法以后进程的运行顺序为：";
    for (const auto& processName : uniqueExecutionOrder) {
        std::cout << processName;
        if (&processName != &uniqueExecutionOrder.back()) {
            std::cout << " --> ";
        }
    }
    std::cout << std::endl;

    std::cout << "\n具体的进程调度信息：" << std::endl;

    std::cout << "进程名\t到达时间\t服务时间\t开始时间\t结束时间\t周转时间\t带权周转时间" << std::endl;
    float totalTurnaroundTime = 0, totalWeightedTurnaroundTime = 0;
    for (const auto& process : processes) {
        std::cout << process.name << "\t"
            << std::fixed << std::setprecision(3) << process.arrivalTime << "\t\t"
            << std::fixed << std::setprecision(3) << process.serviceTime << "\t\t"
            << std::fixed << std::setprecision(3) << process.startTime << "\t\t"
            << std::fixed << std::setprecision(3) << process.endTime << "\t\t"
            << std::fixed << std::setprecision(3) << process.turnaroundTime << "\t\t"
            << std::fixed << std::setprecision(3) << process.weightedTurnaroundTime << std::endl;
        totalTurnaroundTime += process.turnaroundTime;
        totalWeightedTurnaroundTime += process.weightedTurnaroundTime;
    }

    std::cout << "\n平均周转时间为: " << std::fixed << std::setprecision(3) << (totalTurnaroundTime / n) << std::endl;
    std::cout << "平均带权周转时间为: " << std::fixed << std::setprecision(3) << (totalWeightedTurnaroundTime / n) << std::endl;
}

int main() {

    std::cout << "<<----------抢占式短进程优先算法---------->>" << std::endl;
    int n;
    std::cout << "请输入进程数目: ";
    std::cin >> n;

    std::vector<Process> processes(n);
    std::cout << "\n请依次输入各个进程的信息（格式：进程名称 到达时间 服务时间）：" << std::endl;
    for (int i = 0; i < n; ++i) {
        std::cout << "请输入进程 " << i + 1 << "的信息: ";
        std::cin >> processes[i].name >> processes[i].arrivalTime >> processes[i].serviceTime;
        processes[i].remainingTime = processes[i].serviceTime;
    }

    calculateTimes(processes);

    return 0;
}



